Total number of trajectories

Count number of trajectories from 1 to N

Steps (jumps) = 1,2

Performance: O(N)

       ***************                 ****************
       *******                         ********
[------|------|------|------|----------|------|-------]
0      1      2      3      4   ...    N-2    N-1     N
0      0      i ----->                 K[i-2] + K[i-1]

def traj_num(N):
K = [0, 1] + [0] * (N-1)
for i in range(2, N+1):
        K[i] = K[i-2] + K[i-1]
return K[N]

Count all allowed trajectories

Steps (jumps) = 1,2,3

Performance: O(N)

       **********************          **********************
       ***************                 ***************
       *******                         ********
[------|------|------|------|----------|------|-------|------]
0      1      2      3      4   ...    N-3    N-2    N-1     N
0      0      i ----->                 K[i-3]+K[i-2]+K[i-1]
Prohibited cells - in boolean array as False

def count_all_trajectories(N, allowed:list):
    K = [0, 1, int(allowed[2])] + [0] * (N-3)
    for i in range(3, N):
        if allowed[i]:
            K[i] = K[i-1] + K[i-2] + K[i-3]
    return K[N]

Count minimal price to reach N

price[i] - price for cell i
C[i] - min sum price to reach i
steps(jumps): +1 and +2
=> Formula: C[i] = price[i] + min(C[i-1], C[i-2])
C[1] = price[1]
C[2] = price[1] + prcie[2]

def count_min_cost(N, price:list):
    C = [[float("-inf")], price[1], price[1] + price[2]] + [0]*(N-2)
    for i in range(3, N+1):
        C[i] = price[i] + min(C[i-1], C[i-2])
    return C[N]                          # min price to reach N

Test

def test_traj(traj_algorithm):

    print("Testing: ", traj_algorithm.__doc__)
    N = 10

    print("testcase #1: ", end="")
    Exp = 55
    Res = traj_algorithm(N)
    print("Ok" if Res == Exp else "Fail")

if __name__ == "__main__":

    # Trajectories
    test_traj(traj_num)